/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package apriori;

import java.io.BufferedReader;
import java.io.FileReader;
import java.text.NumberFormat;
import java.util.*;

/**
 *
 * @author fredzgw
 */
public class Main {
//all large items
	public static ArrayList<countOfItem> largeItemSet=new ArrayList<countOfItem>();
    //used to judge if large item is empty
	public static ArrayList<ArrayList<countOfItem>> largeItems=new ArrayList<ArrayList<countOfItem>>();  //put all large items
        public static ArrayList<ArrayList<String>> Transaction = new ArrayList<ArrayList<String>>();//Store all the rows
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        try {
            
	    float min_sup=0.5f;
	    float min_con=0.8f;
            String filename = "CommaDelimitedDataset_10_1.csv";
           
            ArrayList<String> rows = new ArrayList<String>();//Used to store one row information
            BufferedReader in = new BufferedReader(new FileReader(filename));
            String s = in.readLine();
            String[] titleList = s.split(",");//Store the title
            ArrayList<ArrayList<String>> ColumSet = new ArrayList<ArrayList<String>>(titleList.length);//Store each column's available value
            
               
                s=in.readLine();
               // System.out.println(s);
           while (s != null && !s.equals("")) {
                rows = new ArrayList<String>();
                rows.clear();
                // System.out.println("fff");
                //  System.out.println(s);
                String[] sl = s.split(",", titleList.length);
                // System.out.println(sl.length);

                for (int i = 0; i < sl.length; i++) {
                 if (sl[i].equals("")) {
                        if (ColumSet.size() < titleList.length) {
                            ArrayList<String> column = new ArrayList<String>();
                            // column.add(titleList[i]+" No");
                            // Collections.sort(column);
                            ColumSet.add(column);
                        }
                    } else {
                        rows.add(titleList[i]+"|"+sl[i]);
                        
                   //     System.out.println(ColumSet.get(i));
                        if (ColumSet.size() < titleList.length) {
                            ArrayList<String> column = new ArrayList<String>();
                            column.add(titleList[i]+"|"+sl[i]);
                            ColumSet.add(column);
                        } else if (!ColumSet.get(i).contains(titleList[i]+"|"+sl[i])) {
                            ColumSet.get(i).add(titleList[i]+"|"+sl[i]);
                        }
                    }

                }
               //  Collections.sort(rows);
              //  System.out.println("rows:"+rows);
                Transaction.add(rows);
                s = in.readLine();
            }
           
            for(int i=0;i<Transaction.size();i++)
            {
              // System.out.println("rows:"+Transaction.get(i));
            }
                   for(int i=0;i<ColumSet.size();i++)
            {
             // System.out.println("Colum:"+ColumSet.get(i));
            }

                oneItemList( min_sup, ColumSet);
             // multiItemList(largeItemSet, min_sup);
             
               apriori(min_sup);

        } catch (Exception e) {
            System.out.println(111 + e.getMessage());
        }

          
    }


	//get all non-empty subsets of an arraylist
	public static ArrayList<ArrayList<String>> allSubSets(ArrayList<String> set)
	{
		ArrayList<ArrayList<String>> subSet = new ArrayList<ArrayList<String>>();
		int num = 1 << set.size();
		int bit;
		int mask = 0; 
		for (int i = 0; i < num;i++ )
		{
			ArrayList<String> itemSet = new ArrayList<String>();
			for (int j = 0; j < set.size(); j++)
			{
				mask = 1 << j;
				bit = i & mask;
				if (bit >0)
				{
					itemSet.add(set.get(j));
				}
			}
			if (itemSet.size() > 0)
			{
				subSet.add(itemSet);
			}
		}
		return subSet;
	}




	//get sup-result
	public static void apriori( float min_sup) throws Exception
	{
	
		for(int k=1;largeItems.get(k-1).size()>0;k++ )
	     {	
                        System.out.println(k+"th time:");
			multiItemList(largeItems.get(k-1),min_sup);
	     }
	
 	    Collections.sort(largeItemSet);
            System.out.println("RESULT COMING...");
         for(int p=0; p<largeItemSet.size(); p++)
         {
        	  NumberFormat nf = NumberFormat.getPercentInstance();
        	  System.out.println(largeItemSet.get(p).getList()+","+nf.format(((float)largeItemSet.get(p).getCount())/Transaction.size()));

         }
	}

	/*
	 *use candidate to get largeitemlist , only keep those with sup>=min_sup
	 */
	public static void multiItemList(ArrayList<countOfItem> lastLargeList, float min_sup) throws Exception
	{
                ArrayList<countOfItem> candidateList=new ArrayList<countOfItem>();
                candidateList=aprioriCandidate(lastLargeList);       //get candidate list from the input lastlargelist

		int sizeOfText=Transaction.size();
		int sizeOfCand=candidateList.size();      //candidate size
		for(int i=0; i<sizeOfText; i++)            //for the whole content
		{
                         // System.out.println(i);
			for(int j=0; j<sizeOfCand; j++)         //for all elements in candidate list
			{
				// System.out.println(i+"th line"+j+"th candidate:"+candidateList.get(j).getList());
				// System.out.println("text content:"+Transaction.get(i));
				//see if item in cand is contained in text
				if(containInText(Transaction.get(i),candidateList.get(j).getList())==true)
				{
					candidateList.get(j).setCount((candidateList.get(j).getCount()+1));
				}


			}
		}
		 ArrayList<countOfItem> tempCandidate=new ArrayList<countOfItem>();
		for(int k=0; k<sizeOfCand; k++)
		{
	               //System.out.println(k+"th candidate is :"+candidateList.get(k).getList());
                       //System.out.println("COUNT IS:"+candidateList.get(k).getCount());
			if(!(((float)(candidateList.get(k).getCount()))/Transaction.size()<min_sup))
			{
				 tempCandidate.add(candidateList.get(k));
				 largeItemSet.add(candidateList.get(k));    //add element into final largeItemSet
			}
		}

		 largeItems.add(tempCandidate);
	  for(int i=0; i<tempCandidate.size(); i++)
          {
                 System.out.println(i+"th item is:"+tempCandidate.get(i).getList());
                 System.out.println("count is:"+tempCandidate.get(i).getCount());
          }
	 }
//if item contained in text, return true
	public static boolean containInText(ArrayList<String> text, ArrayList<String> item)
	{
		for(int i=0; i<item.size(); i++)
		{
			if(!text.contains(item.get(i)))
				return false;
		}
		return true;
	}
	/*
	 * Count L1. input: row items
	 */
	public static void oneItemList(float min_sup, ArrayList<ArrayList<String>> ColumnSet)
	{
		int size=ColumnSet.size();                   //total # of column
		int[] sizeOfColumn=new int[size];             //# of items in one column
	    ArrayList<String> tempList=new ArrayList<String>();     //store all identical items

		/*
		 * For every column, count
		 */
		for(int i=0; i<size; i++)
		{
			sizeOfColumn[i]=ColumnSet.get(i).size();
		    for(int j=0; j<sizeOfColumn[i]; j++)
		    {
		    	if(!tempList.contains(ColumnSet.get(i).get(j)))
		    	{
		    		tempList.add(ColumnSet.get(i).get(j));
		    	}
		    }

		}
  
		for(int index=0; index<tempList.size(); index++)
		{
			ArrayList<String> smallList=new ArrayList<String>();
			smallList.clear();
			smallList.add(tempList.get(index));         //get every item in tempList
			countOfItem itemWithCount=new countOfItem(smallList);
			/*
			 * check the whole text, to count the totlal line # of item appear
			 */
			for(int t=0; t<Transaction.size(); t++)
			{
				if(Transaction.get(t).contains(tempList.get(index)))
				{
					itemWithCount.setCount(itemWithCount.getCount()+1);
				}
			}
			//if sup of the item is >= min_sup, put it into the largeList
			if(!(((float)(itemWithCount.getCount()))/Transaction.size()<min_sup))
			{
				largeItemSet.add(itemWithCount);    //add element into final largeItemSet
			}
		}
		largeItems.add(largeItemSet);
		 for(int i=0; i<largeItemSet.size(); i++)
		 {
			 // System.out.println(i+"th largeItem is:"+largeItemSet.get(i).getList());
			//  System.out.println("it's count is:"+largeItemSet.get(i).getCount());
		 }
                
	}


	//get candidate from last large item sets
	public static ArrayList<countOfItem> aprioriCandidate(ArrayList<countOfItem> lastLargeItemSet) throws Exception
	{
		ArrayList<countOfItem> newLargeItemSet=new ArrayList<countOfItem>();
		for(int i=0; i<lastLargeItemSet.size(); i++)
		{
			for(int j=i+1; j<lastLargeItemSet.size(); j++)
			{
				ArrayList<String> listI=new ArrayList<String>();
				ArrayList<String> listJ=new ArrayList<String>();
				ArrayList<String> listITemp=new ArrayList<String>();
				ArrayList<String> listJTemp=new ArrayList<String>();

				listI=lastLargeItemSet.get(i).getList();
				listJ=lastLargeItemSet.get(j).getList();
				int size=listI.size();
				//first i-1 elements
				for(int indexOfI=0; indexOfI<size-1;indexOfI++)
				{
					listITemp.add(listI.get(indexOfI));
				}
				//first i-1 elements
				for(int indexOfJ=0; indexOfJ<size-1; indexOfJ++)
				{
					listJTemp.add(listJ.get(indexOfJ));
				}
				/*
				 * if all elements in the two arraylists except for the last one are equal
				 * and the last element of the first arraylist < the last element of the
				 * second arraylist, do the joining step
				 */
				if((listITemp.equals(listJTemp))&&(listI.get(size-1).compareTo(listJ.get(size-1))!=0))
				{
				 	countOfItem joinItemWithCount=new countOfItem(joinItem(listI, listJ));
					newLargeItemSet.add(joinItemWithCount);        //add them to a new list
				}
			}
		}

		/*
	     * Prune step. Delect all subsets in newListSet whose subset is not in
		 * newListSet
	     */
			pruneItem(newLargeItemSet, lastLargeItemSet);
			  for(int p=0; p<newLargeItemSet.size(); p++)
			 {
				// System.out.println(p+"th new is:" +newLargeItemSet.get(p).getList());
                               //  System.out.println("it's sup is:"+newLargeItemSet.get(p).getCount());
			 }
		    return newLargeItemSet;
	}

	//join two items
	public static ArrayList<String> joinItem(ArrayList<String> listI, ArrayList<String> listJ)
	{
		ArrayList<String> newList=new ArrayList<String>();
		/*
		 * join two arrayLists with all elements of the
		 * first one and the last element of the second one
		 */
		for(int index=0; index<listI.size(); index++)
		{
			newList.add(listI.get(index));
		}
	     newList.add(listJ.get(listJ.size()-1));
		 return newList;
	}

	//prune old possible candidate, get candidate, candidate is the new PossibleLargeList
	public static void pruneItem(ArrayList<countOfItem> newPossibleLargeList, ArrayList<countOfItem> lastLargeList) throws Exception
	{
		int size=newPossibleLargeList.size();
		/*
		 * For all items in newListSet, delete those with subsets that
		 * is not contained in myList
		 */
		for(int i=0; i<size; i++)
		{

		   for(int j=0; j<subSet(newPossibleLargeList.get(i).getList()).size(); j++)
		   {
			  /*
			   * if one of the subset is not contained in myList,
			   * delete the newListSet
			   */
			   ArrayList<ArrayList<String>> lastLargeListOnly=new ArrayList<ArrayList<String>>();
			   for(int p=0; p<lastLargeList.size(); p++)
				   lastLargeListOnly.add(lastLargeList.get(p).getList());
			   if(!lastLargeListOnly.contains(subSet(newPossibleLargeList.get(i).getList()).get(j)))
			   {
				   newPossibleLargeList.remove(i);
				   size--;
				   i--;
				   break;
			   }
		   }
		}
	}

	//Get all subsets with i-1 items of a list
	public static ArrayList<ArrayList<String>> subSet(ArrayList<String> fatherList) throws Exception
	{
		int sizeOfFather=fatherList.size();
		ArrayList<ArrayList<String>> subListSet=new ArrayList<ArrayList<String>>();
		subListSet.clear();
		for(int i=0; i<sizeOfFather; i++)
		{
			 ArrayList<String> subList=new ArrayList<String>();
			 subList.clear();
			/*
			 * Get sublists before i
			 */
			for(int j=0; j<i; j++)
			{
				subList.add(fatherList.get(j));

			}
			/*
			 * Get sublists after i
			 */
			for(int k=i+1; k<sizeOfFather; k++)
			{
				subList.add(fatherList.get(k));

			}

			 subListSet.add(subList);
		}


		return subListSet;
	}
	
}

 
